package clustering_algorithms;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

public class k_means_plus extends k_means{

	public k_means_plus(ArrayList<HashMap<Integer, Float>> vectors_to_cluster,
			int number_of_clusters, float maximal_centroid_movement)
			throws IOException {
		super(vectors_to_cluster, number_of_clusters, maximal_centroid_movement);
	}
	
	protected ArrayList<Integer> ChooseSeeds()
	{
		Random rand = new Random();
	    //return picked;
	    Set<Integer> chosen_seeds = new HashSet<Integer>();
	    //pick one at random
	    // create a distributed randomization
	    int first_seed_chosend = rand.nextInt(m_vectors_to_cluster.size());
	    chosen_seeds.add(first_seed_chosend);
	    
	    for (int i =1; i < m_number_of_clusters; ++i)
	    {
	    	TreeMap<Float, Integer> random_distributaion = new TreeMap<Float, Integer>();
	    	float sum_of_distances = 0f;
	    	for(int doc_id = 0; doc_id < m_vectors_to_cluster.size(); ++doc_id)
	    	{
	    		if (chosen_seeds.contains(doc_id) )
	    		{
	    			continue;
	    		}
	    		float min_distance = Float.MAX_VALUE;
	    		for(Integer centroid_id : chosen_seeds)
	    		{
	    			float distance = CalcEuclidianDistance(m_vectors_to_cluster.get(centroid_id),m_vectors_to_cluster.get(doc_id));
	    			if(distance < min_distance)
	    			{
	    				min_distance = distance; 
	    			}
	    		}
	    		sum_of_distances += min_distance;
	    		random_distributaion.put(sum_of_distances, doc_id);
	    		
	    	}
	    	
    		float minX = 0f;
    		float maxX = sum_of_distances;

    		

    		float finalX = rand.nextFloat() * (maxX - minX) + minX;
	    	
	    	Entry<Float, Integer> chosen_seed_entry = random_distributaion.ceilingEntry(finalX);
    		
    		chosen_seeds.add(chosen_seed_entry.getValue());
	    		    	
	    }
	    
	    ArrayList<Integer> return_value = new ArrayList<Integer>();
	    for(int seed : chosen_seeds )
	    {
	    	return_value.add(seed);
	    }
		return return_value;		
	}
	
	
	
	

}